package BinaryTree.CompleteBinaryTree;

/**
 * question: 求一个完全二叉树的节点个数
 *
 * @author Liaorun
 */
public class CompleteBinaryTreeNodeNumber {

    public static void main(String[] args) {
        Node head = new Node(1);
        head.left = new Node(2);
        head.right = new Node(3);
        head.left.left = new Node(4);
        head.left.right = new Node(5);

        System.out.println(nodeNum(head));
    }

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int value) {
            this.value = value;
        }
    }


    public static int nodeNum(Node head) {
        if (head == null) {
            return 0;
        }

        return bs(head, 1, mostLeftLevel(head, 1));
    }

    /**
     * @param node  当前节点
     * @param level 当前节点的深度
     * @param h     二叉树的高度
     * @return
     */
    private static int bs(Node node, int level, int h) {
        if (level == h) {
            return 1;
        }

        if (mostLeftLevel(node.right, level + 1) == h) {
            // node 的左子树是满二叉树 且好的为 node的高度 = h - level
            return (1 << (h - level)) + bs(node.right, level + 1, h);
        } else {
            // node 的左子树不是满二叉树，但是右子树是满二叉树 且 高度 =  node的高度 - 1 = h - level - 1
            return (1 << (h - level - 1)) + bs(node.left, level + 1, h);
        }
    }

    /**
     * 获取二叉树最左侧的深度
     *
     * @param head  子树根节点
     * @param level 子树根节点深度
     * @return
     */
    private static int mostLeftLevel(Node head, int level) {

        while (head != null) {
            level++;
            head = head.left;
        }

        // -1 是上面的循环会多加一次
        return level - 1;
    }
}
